package 中等.搜索.广度优先搜索;

import util.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
 * 注意，根节点 root 位于深度 1 。
 * 加法规则如下:
 * 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
 * cur 原来的左子树应该是新的左子树根的左子树。
 * cur 原来的右子树应该是新的右子树根的右子树。
 * 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/add-one-row-to-tree
 */
public class 在二叉树中增加一行_623 {

    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;

        addOneRow2(node1, 5, 4);

    }

    /**
     * 广度优先搜索
     *
     * @param root
     * @param val
     * @param depth
     * @return
     */
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        int curDepth = 1;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            if (curDepth == depth - 1) {
                while (size-- > 0) {
                    TreeNode curNode = queue.pollFirst();
                    TreeNode leftNode = curNode.left;
                    TreeNode rightNode = curNode.right;

                    curNode.left = new TreeNode(val);
                    curNode.right = new TreeNode(val);

                    curNode.left.left = leftNode;
                    curNode.right.right = rightNode;
                }
                break;
            }

            while (size-- > 0) {
                TreeNode curNode = queue.pollFirst();
                if (curNode.left != null) {
                    queue.addLast(curNode.left);
                }
                if (curNode.right != null) {
                    queue.addLast(curNode.right);
                }
            }
            curDepth++;
        }
        return root;
    }

    /**
     * 深度优先搜索
     *
     * @param root
     * @param val
     * @param depth
     * @return
     */
    public static TreeNode addOneRow2(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }

        dfs(root, 1, val, depth);
        return root;
    }

    private static void dfs(TreeNode node, int curDepth, int val, int depth) {
        if (curDepth == depth - 1) {
            TreeNode leftNode = node.left;
            TreeNode rightNode = node.right;

            node.left = new TreeNode(val);
            node.right = new TreeNode(val);

            node.left.left = leftNode;
            node.right.right = rightNode;
            return;
        }
        if (node.left != null) {
            dfs(node.left, curDepth + 1, val, depth);
        }
        if (node.right != null) {
            dfs(node.right, curDepth + 1, val, depth);
        }
    }
}
